import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class MyHeap {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Test();
    }
    public static void Test(){
        PriorityQueue<Integer> smallQueue = new PriorityQueue<>();
        PriorityQueue<Integer> bigQueue = new PriorityQueue<>(new IntCmp());
        smallQueue.add(15);
        smallQueue.add(48);
        smallQueue.add(59);
        smallQueue.add(6);
        smallQueue.add(37);
        smallQueue.add(89);
        smallQueue.add(45);
        smallQueue.add(1);
        smallQueue.add(20);
        bigQueue.add(15);
        bigQueue.add(48);
        bigQueue.add(59);
        bigQueue.add(6);
        bigQueue.add(37);
        bigQueue.add(89);
        bigQueue.add(45);
        bigQueue.add(1);
        bigQueue.add(20);
        System.out.println(smallQueue);
        System.out.println(bigQueue);
    }
    public int[] elem;
    public int usedSize;
    public MyHeap(){
        elem = new int[10];
    }
    //创建一个大根堆
    public void creative1(int[] arr){
        for(int i = 0;i < arr.length;i++){
            if(isFull()){
                elem = Arrays.copyOf(elem,elem.length * 2);
            }
            elem[i] = arr[i];
            usedSize++;
        }
    }
    public void doArr(){
        //最后一个叶子结点的父结点
        int start = (usedSize - 1 - 1) / 2;
        for(int i = start;i >= 0;i--){
            siftDown(i,usedSize);
        }
    }
    //将较大的子节点与父结点交换
    //向下调整
    public void siftDown(int parent,int end){
        //找到父结点的的左子结点
        int child = parent * 2 + 1;
        //保证该子结点未越界
        while(child < end){
            //查找左右子结点中的最大子结点
            //(包含了找出最大值后,对右子节点的判断)
            if(child + 1 < end && elem[child] < elem[child + 1]){
                child++;
            }
            //判断是否需要与父结点交换(判断大小)
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    //向堆中添加新元素
    public void offer(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }
    //向上调整
    public void siftUp(int child){
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }
    //删除元素
    public int poll(){
        int oldValue = elem[0];
        elem[0] = elem[--usedSize];
        siftDown(0,usedSize);
        return oldValue;

    }
    //将堆排序成从小到大的顺序
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){
            int tmp = elem[end];
            elem[end] = elem[0];
            elem[0] = tmp;
            siftDown(0,end);
            end--;
        }
    }
    public boolean isFull(){
        return usedSize >= elem.length;
    }
}